package demo.tree;

/**
 * 是否是平衡二叉树
 */
public class IsBalanced {
    public static void main(String[] args) {
        Node head = TreeUtil.treeBuild();

        System.out.println("");
        System.out.println("判断是否是平衡二叉树");
        System.out.println(isBalanceTree(head));
        System.out.println();
        System.out.println();
    }

    public static boolean isBalanceTree(Node node) {
        return process2(node).isBalanced;
    }

    /**
     * 二叉树的递归套路
     *
     * @param x
     * @return
     */
    public static Info process2(Node x) {
        if (x == null) {
            return new Info(true, 0);
        }

        Info leftInfo = process2(x.left);
        Info rightInfo = process2(x.right);

        int height = Math.max(leftInfo.height, rightInfo.height) + 1;

        boolean isBalance = true;
        if (!leftInfo.isBalanced || !rightInfo.isBalanced || Math.abs(leftInfo.height - rightInfo.height) > 1) {
            isBalance = false;
        }

        return new Info(isBalance, height);
    }

    private static class Info {
        public boolean isBalanced;
        public int height;

        public Info(boolean isBalanced, int height) {
            this.isBalanced = isBalanced;
            this.height = height;
        }
    }
}
